package com.example.algorithm.a;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
import java.util.Vector;

/**
 * @author: dangwen
 * @createDate: 2021/3/29
 * 1、1、2、3、5、8、13、21、34、……
 */

public class FibonacciSequence {

    /**
     * 递归：暴力解法
     * @param n
     * @return
     */
    public static int fib1(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        return fib1(n-1) + fib1(n-2);
    }

    /**
     * 带有备忘录的解法，减少无效计算
     * @param n
     * @return
     */
    public static int fib2(int n){
        if(n < 1) {
            return 0;
        }
        Hashtable<Integer,Integer> hashtable = new Hashtable();
        return helper(hashtable, n);
    }
    public static int helper(Hashtable<Integer,Integer> hashtable, int n ){
        if(n == 1 || n ==2){
            return 1;
        }
        if(hashtable.containsKey(n)){
            System.out.println("----------------查询节点为" + n + "数据时，使用了备忘录");
            return hashtable.get(n);
        }
        // TODO 这里还有一点问题，就是哈希表中多存放了两个无须存放的数据（n 和 n-1），该如何完美去掉
        hashtable.put(n, helper(hashtable, n-1) + helper(hashtable, n - 2));
        return helper(hashtable, n-1) + helper(hashtable, n - 2);
    }


    /**
     * 终极做法
     * @param n
     * @return
     */
    public static int fib(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        int pre = 1, curr = 1, sum;
        for(int i = 3; i <= n; i++){
            sum = pre + curr;
            pre = curr;
            curr = sum;
        }
        return curr;
    }

    public static void main(String[] args) {
//        for (int i = 1; i < 10; i++) {
//            System.out.println(fib2(i));
//        }
//        String s;
        int s;
//        System.out.println("s="+s);

//        Integer.valueOf()
    }

}
